#include <stdio.h>
#define INF 100000
void sort(int *arr,int idx);
int main(){
	int arr[INF]={0};
	int n=0;
	printf("Please input n:");
	scanf("%d",&n);
	int i1=0;
	for(i1=0;i1<n;i1++)
		scanf("%d",&arr[i1]);
	for(i1=0;i1<n;i1++)
		printf("%d\t",arr[i1]);
	printf("\n");	
	sort(arr,n-1);
	for(i1=0;i1<n;i1++)
		printf("%d\t",arr[i1]);
	printf("\n");	
	return 0;
}

void sort(int *arr,int idx){
	if(idx==0){
	}else{
		sort(arr,idx-1);
		int key=arr[idx];
		int i=idx-1;
		while(i>=0 && key<arr[i]){
			arr[i+1]=arr[i];
			i--;
		}
		arr[i+1]=key;
	}
}
